//
// Description: 55. 跳跃游戏
// Created by Loading on 2021/4/3.
//

#include <bits/stdc++.h>

using namespace std;

//贪心算法
bool canJump(vector<int> &nums) {
    //可以到达的最远距离
    //每个元素可以到达的最远距离为：nums[i] + i
    int far_most = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i <= far_most) {
            //更新可以到达的最远距离
            far_most = max(far_most, nums[i] + i);
            if (far_most >= nums.size() - 1) {//可以到达
                return true;
            }
        } else {//再也无法到达
            return false;
        }
    }

    return false;
}

int main() {
    vector<int> nums = {3, 2, 1, 0, 100, 4};
    cout << canJump(nums) << endl;
}